#pragma once

#include <stdlib.h>
#include <stdio.h>

typedef struct _Freqperchar {
	unsigned char c;
	size_t cnt;
	unsigned char encodebits;
	size_t code;
} Freqperchar;

typedef struct _TreeNode {
	size_t cnt;
	Freqperchar* leaf;
	struct _TreeNode* left;
	struct _TreeNode* right;
} TreeNode;

typedef struct _ListNode {
	size_t cnt;
	struct _TreeNode* tree;
	struct _ListNode* next;
} ListNode;

void assigncode(const TreeNode* tree, size_t level, size_t code, size_t* length)
{
	Freqperchar* freqleaf = tree->leaf;
	if (freqleaf) {
		// printf("at level %d: code = %lld\n", level, code);
		freqleaf->encodebits = (unsigned char)level;
		freqleaf->code = code;
		*length += level * freqleaf->cnt;
		return;
	}
	// printf("go left\n");
	assigncode(tree->left, level + 1, (code << 1), length);
	// printf("go up and right\n");
	assigncode(tree->right, level + 1, (code << 1) + 1, length);
}

int sortbycnt(const void* a, const void* b)
{
	return ((Freqperchar*)a)->cnt - ((Freqperchar*)b)->cnt;
}

int sortbyc(const void* a, const void* b)
{
	return (*(Freqperchar * *)a)->c - (*(Freqperchar * *)b)->c;
}